/**
 * 421. 数组中两个数的最大异或值
 * 中等
 * <p>
 * 给你一个整数数组 nums ，返回 nums[i] XOR nums[j] 的最大运算结果，其中 0 ≤ i ≤ j < n 。
 * 示例 1：
 * <p>
 * 输入：nums = [3,10,5,25,2,8]
 * <p>
 * 输出：28
 * <p>
 * 解释：最大运算结果是 5 XOR 25 = 28.
 * <p>
 * 示例 2：
 * <p>
 * 输入：nums = [14,70,53,83,49,91,36,80,92,51,66,70]
 * <p>
 * 输出：127
 * <p>
 * 提示：
 * <p>
 * 1 <= nums.length <= 2 * 105
 * 0 <= nums[i] <= 231 - 1
 */

public class MaximumXorOfTwoNumbersInAnArray {

    public static void main(String[] args) {
        System.out.println(findMaximumXOR(new int[]{2, 4}));
        System.out.println(findMaximumXOR(new int[]{3, 10, 5, 25, 2, 8}));
        System.out.println(findMaximumXOR(new int[]{14, 70, 53, 83, 49, 91, 36, 80, 92, 51, 66, 70}));
    }

    public static int findMaximumXOR(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return 0;
        }
        PreTree preTree = new PreTree();
        preTree.add(nums[0]);
        int max = 0;
        for (int i = 1; i < nums.length; i++) {
            max = Math.max(preTree.max(nums[i]), max);
            preTree.add(nums[i]);
        }
        return max;
    }
}

class PreTree {
    private final Node head = new Node();

    void add(int num) {
        Node cur = this.head;
        for (int move = 31; move >= 0; move--) {
            int path = (num >> move) & 1;
            cur.next[path] = cur.next[path] == null ? new Node() : cur.next[path];
            cur = cur.next[path];
        }
    }

    int max(int num) {
        int target = 0;
        Node cur = this.head;
        for (int move = 31; move >= 0; move--) {
            int path = (num >> move) & 1;
            int best = 0;
            if (move != 31) {
                best = path ^ 1;
            }
            best = cur.next[best] != null ? best : best ^ 1;
            target |= ((path ^ best) << move);
            cur = cur.next[best];
        }
        return target;
    }
}


class Node {
    final Node[] next = new Node[2];
}